package com.lw.leetcode.greedy.c;

/**
 * Created with IntelliJ IDEA.
 * 2366. 将数组排序的最少替换次数
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/8 16:47
 */
public class MinimumReplacement {

    public static void main(String[] args) {
        MinimumReplacement test = new MinimumReplacement();


        // 2
//        int[] arr = {3, 9, 3};

        // 0
//        int[] arr = {1, 2, 3, 4, 5};

        // 0
//        int[] arr = {15, 7};

        // 73
        int[] arr = {19, 7, 2, 24, 11, 16, 1, 11, 23};

        long l = test.minimumReplacement(arr);
        System.out.println(l);
    }

    public long minimumReplacement(int[] nums) {
        int l = nums.length - 2;
        long count = 0;
        int n = nums[l + 1];
        for (int i = l; i >= 0; i--) {
            int v = nums[i];
            if (v <= n) {
                n = v;
                continue;
            }
            int c = (v + n - 1) / n;
            count += (c - 1);
            n -= (c * n - v + c - 1) / c;
        }
        return count;
    }

}
